[Not Applicable]
[Not Applicable]
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the U.S. Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever.
A microfiche appendix of the presently preferred computer program source code is included and comprises 1 sheets and a total of 91 frames.
The Microfiche Appendix is hereby expressly incorporated herein by reference, and contains material which is subject to copyright protection as set forth above.
The present invention generally relates to software compiler technology. More particularly, the present invention relates to a method for computing definition-use information for lvalues that may be aggregates and/or referenced through pointer expressions.
Within the field of compilers, the problem of determining which definitions reach uses in a program is important to many optimizations. For the case where the left sides of definitions are scalars, the problem is well understood. One prior-art technique generalizes the analysis to definitions whose left sides are aggregates and/or pointer expressions. The generalization to aggregates is based on partitioning an aggregate into components, and tracking each component separately. The generalization to lvalues referenced through pointer expressions is based on using two data-flow solvers. A bottom level solver tracks whether a pointer expression to the lvalue changes between the point of definition and point of use, and a top level solver employs said information about said changes to determine where the lvalues reach.
This prior art technique has a number of disadvantages.
(a) It requires two data-flow solvers, which can be expensive in time and memory storage requirements. Particularly expensive in terms of space is the requirement that the results of the bottom analyzer be retained while the top analyzer runs.
(b) It requires up to 9 bits of data-flow solution per definition in the data-flow problems solved. Specifically, the bottom-level solver operates on a lattice of 3-bit vectors, and requires two such vectors for each definition analyzed, one for the address of the defined lvalue, and one for the support of the right side. Thus the bottom-level solver requires up to 6 bits per definition to represent a lattice value. The top-level solver requires yet another 3-bit vector value for each partitioned piece of the lvalue defined by the definition. Furthermore, for each bit in any said vector, there are three possible monotone lattice functions, thus two bits are required to represent each lattice function on a bit. Consequently, for a definition partitioned into n pieces, the solvers need 6+3n bits and 12+6n bits respectively to represent the lattice values and functions related to a single definition.
(c) It fails to find some opportunities for forward substitution, because the bottom solver sometimes reports changes in right sides of definitions that were actually irrelevant because the corresponding definition is no longer live along the paths for which the change occurred. FIG. 1A and FIG. 1B show such an example. Definitions 100 and 101 both reach the use 102 of p in xe2x80x9cq=pxe2x80x9d. Both have the form xe2x80x9cp=x[j]xe2x80x9d. The support of x[j] is the set of lvalues {x,j}. If the statement 103 xe2x80x9cj=j+1xe2x80x9d is executed, then the support of the right side of definition 100 will have changed between its point of definition and the statement xe2x80x9cq=pxe2x80x9d. The prior art interprets the change as preventing forward substitution. However, along paths including xe2x80x9cj=j+1xe2x80x9d, definition 100 is dead, and thus would be correct to forward substitute x[j] for p in xe2x80x9cq=pxe2x80x9d.
(d) It fails to find some opportunities for removing dead stores or scalar replacement, because the bottom solver sometimes reports changes to the support of left sides of definitions that were actually irrelevant because the corresponding definition is no longer live along the paths for which the change occurred. The problem is similar in flavor to said problem with right sides, though the consequent inferiority is different. FIG. 2A and FIG. 2B show such an example. Definition 200 is never used, because it is killed by either definition 201 or 202, depending upon the path taken. The support of the left side of definition 200 includes k, and along paths through definition 201, the value of k changes 203. Unfortunately, when the top-level solver of said prior art inspects definition 202 to check whether it kills definition 200, the bottom-level solver reports that k changed along some paths and consequently the top-level solver must assume that definition 202 does not kill definition 200.
Accordingly, the present invention provides a method and apparatus that analyzes definitions and uses of lvalues in a program. For each definition in the program, the method computes where the definition reaches, and whether the support of the definition""s left side has changed while the definition is live. The method according to the present invention can also be implemented by computing where each use reaches backwards within a program, and whether the support of the use changes while the use is live. The present invention also demonstrates a novel way of representing lattice elements with binary codes. The lattice is embedded in a boolean hypercube, and binary codes are assigned corresponding to the hypercube coordinates. The codes are then compacted by removing some bit positions and duplicate codes removed by complementing a few bits in some of the codes.